#pragma once
#include <stdexcept>
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10

namespace DS {
	template <class T>
	class stack {
	private:
		T* base_ptr;
		T* top_ptr;
		int stackSize;
		int stackCapacity;
	public:
		stack();
		void push(T const&);
		void pop();
		T top() const;
		int size() const;
		bool empty() const;
		T at(int) const;
	};

	template <class T>
	stack<T>::stack() {
		base_ptr = (T*)malloc(STACK_INIT_SIZE * sizeof(T));
		if (!base_ptr) {
			throw std::overflow_error("Stack<>::Stack(): init stack failed");
		}
		top_ptr = base_ptr;
		stackSize = 0;
		stackCapacity = STACK_INIT_SIZE;
	}

	template <class T>
	void stack<T>::push(T const& elem)
	{
		if (stackSize >= stackCapacity) {
			stackCapacity += STACK_INCREMENT;
			base_ptr = (T*)realloc(base_ptr, (stackCapacity) * sizeof(T));
		}
		if (!base_ptr) {
			throw std::overflow_error("Stack<>::Stack(): stack overflow");
		}
		top_ptr++;
		*top_ptr = elem;
		stackSize++;
	}

	template <class T>
	void stack<T>::pop()
	{
		if (empty()) {
			throw std::underflow_error("Stack<>::pop(): empty stack");
		}
		top_ptr--;
		stackSize--;
	}

	template <class T>
	T stack<T>::top() const
	{
		if (empty()) {
			throw std::out_of_range("Stack<>::top(): empty stack");
		}
		return *top_ptr;
	}

	template <class T>
	int stack<T>::size() const {
		return stackSize;
	}

	template <class T>
	bool stack<T>::empty() const {
		return top_ptr == base_ptr;
	}

	template <class T>
	T stack<T>::at(int n) const {
		if (n >= stackSize) {
			throw std::out_of_range("Stack<>::at(): element not exists");
		}
		return *(base_ptr + n + 1);
	}
}